Corelab Seminar
2013-2014
Manolis Zampetakis (NTUA)
Mechanism Design with Verification
Abstract.
The basic mechanism design model assumes that each agent can follow any of its strategies,
independently of its type. Thus the mechanism cannot use any "real-world" information about the agents.
This is the norm in mechanism design and it models well the negotiation stage in which agents do nothing but
communicate. A simple type of modification to the model suggests itself: a problem definition may limit the set
of strategies A_i available to each agent as a function of its type t_i. In this work we investigate the way
mechanism design changes under the assumption of verification.
The first deference in the mechanism design with verification is the existence of non-truthful implementations
of social choice functions. We present the reason why this way of implementation is not really helpful in the
solution concept of dominant strategy equilibrium and we present a way it could be useful using the concept of Nash equilibrium.
In this work, we also investigate the reasons that make symmetric partial
verification essentially useless in virtually all domains. Departing from previous
work, we consider any possible (finite or infinite) domain and general symmetric
verification. We identify a natural property, namely that the correspondence graph of a symmetric verification M
is strongly connected by finite paths along which the preferences are consistent with the preferences at the endpoints,
and prove that this property is sufficient for the equivalence of truthfulness and M -truthfulness. Since the simplest
symmetric verification is the local verification, specific cases of our result are closely related, in the case without
money, to the research about the equivalence of local truthfulness and global truthfulness.
To complete the picture, we consider asymmetric verification, and prove that a social choice function is M -truthfully
implementable by some asymmetric verification M if and only if f does not admit a cycle of profitable deviations.